package code;

import java.util.Deque;
import java.util.LinkedList;
import java.util.List;
import java.util.Queue;
import java.util.concurrent.LinkedBlockingQueue;

/**
 * 描述:树的前序中序后序层序遍历
 *
 * @author Madison You
 * @created 18:32
 */
public class Tree {
    public static void main(String[] args) {
        TreeNode[] treeNodes = new TreeNode[10];
        for (int i = 0; i < 10; i++) {
            treeNodes[i] = new TreeNode(i + 1);
        }
        for (int i = 0; i < 10; i++) {
            if (i * 2 + 1 < 10) {
                treeNodes[i].left = treeNodes[i * 2 + 1];
            }
            if (i * 2 + 2< 10) {
                treeNodes[i].right = treeNodes[i * 2 + 2];
            }
        }
        preOrderRe3(treeNodes[0]);
    }


    public static void preOrderRe1(TreeNode treeNode) {
        if (treeNode != null) {
            System.out.println(treeNode.value);
            preOrderRe1(treeNode.left);
            preOrderRe1(treeNode.right);
        }
    }

    public static void preOrderRe2(TreeNode treeNode) {
        Deque<TreeNode> deque = new LinkedList<>();
        while (!deque.isEmpty() || treeNode != null) {
            while (treeNode != null) {
                System.out.println(treeNode.value);
                deque.push(treeNode);
                treeNode = treeNode.left;
            }
            treeNode = deque.pop();
            treeNode = treeNode.right;
        }
    }

    public static void preOrderRe3(TreeNode treeNode) {
        Deque<TreeNode> st = new LinkedList<>();
        if (treeNode != null) st.push(treeNode);
        while (!st.isEmpty()) {
            TreeNode node = st.peek();
            if (node != null) {
                st.pop();  //将该节点弹出，避免重复操作，下面再将右中左节点添加到栈中
                if (node.right!= null) st.push(node.right); //添加右节点（空节点不入栈）
                if (node.left != null) st.push(node.left);  //添加左节点（空节点不入栈）
                st.push(node);  //添加中节点
                st.push(null);  //中节点访问过，但是还没有处理，加入空节点做为标记
            } else {  //只有遇到空节点的时候，才将下一个节点放进结果集
                st.pop();  //将空节点弹出
                node = st.peek();  //重新取出栈中元素
                st.pop();
                System.out.println(node.value); //输出结果集
            }
        }
    }

    public static void midOrderRe1(TreeNode treeNode) {
        if (treeNode != null) {
            midOrderRe1(treeNode.left);
            System.out.println(treeNode.value);
            midOrderRe1(treeNode.right);
        }
    }

    public static void midOrderRe2(TreeNode treeNode) {
        Deque<TreeNode> deque = new LinkedList<>();
        while (!deque.isEmpty() || treeNode != null) {
            while (treeNode != null) {
                deque.push(treeNode);
                treeNode = treeNode.left;
            }
            if (!deque.isEmpty()) {
                treeNode = deque.pop();
                System.out.println(treeNode.value);
                treeNode = treeNode.right;
            }
        }
    }

    public static void midOrderRe3(TreeNode treeNode) {
        Deque<TreeNode> st = new LinkedList<>();
        if (treeNode != null) st.push(treeNode);
        while (!st.isEmpty()) {
            TreeNode node = st.peek();
            if (node != null) {
                st.pop();  //将该节点弹出，避免重复操作，下面再将右中左节点添加到栈中
                if (node.right!= null) st.push(node.right); //添加右节点（空节点不入栈）
                st.push(node);  //添加中节点
                st.push(null);  //中节点访问过，但是还没有处理，加入空节点做为标记
                if (node.left != null) st.push(node.left);  //添加左节点（空节点不入栈）
            } else {  //只有遇到空节点的时候，才将下一个节点放进结果集
                st.pop();  //将空节点弹出
                node = st.peek();  //重新取出栈中元素
                st.pop();
                System.out.println(node.value); //输出结果集
            }
        }
    }

    public static void postOrderRe1(TreeNode treeNode) {
        if (treeNode != null) {
            postOrderRe1(treeNode.left);
            postOrderRe1(treeNode.right);
            System.out.println(treeNode.value);
        }
    }

    public static void postOrderRe3(TreeNode treeNode) {
        Deque<TreeNode> st = new LinkedList<>();
        if (treeNode != null) st.push(treeNode);
        while (!st.isEmpty()) {
            TreeNode node = st.peek();
            if (node != null) {
                st.pop();  //将该节点弹出，避免重复操作，下面再将右中左节点添加到栈中
                st.push(node);  //添加中节点
                st.push(null);  //中节点访问过，但是还没有处理，加入空节点做为标记
                if (node.right!= null) st.push(node.right); //添加右节点（空节点不入栈）
                if (node.left != null) st.push(node.left);  //添加左节点（空节点不入栈）
            } else {  //只有遇到空节点的时候，才将下一个节点放进结果集
                st.pop();  //将空节点弹出
                node = st.peek();  //重新取出栈中元素
                st.pop();
                System.out.println(node.value); //输出结果集
            }
        }
    }

    public static void levelOrderRe(TreeNode treeNode) {
        Queue<TreeNode> queue = new LinkedBlockingQueue<>();
        queue.offer(treeNode);
        while (!queue.isEmpty()) {
            int size = queue.size();
            for (int i = 0; i < size; i++) {
                TreeNode node = queue.poll();
                System.out.println(node.value);
                if (node.left != null) {
                    queue.offer(node.left);
                }
                if (node.right != null) {
                    queue.offer(node.right);
                }
            }
        }
    }

}


class TreeNode//节点结构
{
    int value;
    TreeNode left;
    TreeNode right;

    TreeNode(int value) {
        this.value = value;
    }
}
